home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Tree / D_Node.h < prev    next >
C/C++ Source or Header  |  1992-05-15  |  10KB  |  242 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 07/11/89 -- Initial design
  13. // Updated: MBN 08/10/89 -- Initial implementation
  14. // Updated: MBN 08/11/89 -- Inherit from Generic
  15. // Updated: MBN 09/19/89 -- Added conditional exception handling
  16. // Updated: MBN 12/21/89 -- Added optional argument to set_compare method
  17. // Updated: MBN 02/27/90 -- Added operator= for pointer argument
  18. // Updated: MJF 03/12/90 -- Added group names to RAISE
  19. // Updated: VDN 02/21/92 -- New lite version and fix memory leaks
  20. //
  21. // The D_Node<Type,nchild> class implements parameterized  nodes of  a  dynamic
  22. // size for N-ary  trees.   This node class  is parameterized for  the type and
  23. // some initial  "N",  the   number  of  subtrees  each  node may   have.   The
  24. // D_Node<Type,nchild>  class  is dynamic   in  the  sense that the   number of
  25. // subtrees allowed for each  node is not  fixed.  D_Node<Type,nchild> utilizes
  26. // the Vector<Type>  class,  supporting runtime growth charactersitics.    As a
  27. // result, the D_Node<Type,nchild> class  should be  used as the node  type for
  28. // the N_Tree<Node,Type,nchild> class when  the number of subtrees is variable,
  29. // unknown at  compile time, or   needs to  increase on   a per-node  basis  at
  30. // runtime.  This capability is suited for heirarchical trees such as  might be
  31. // used  in an   organization  chart.   In  addition,   specialization  of  the
  32. // N_Tree<Node,Type,nchild>  class  would  allow   for  the   relatively   easy
  33. // implementation of a Diagram class.
  34. //
  35. // There are three public constructors for the  D_Node class to allow  the user
  36. // to  create nodes and  control the building and   structure of an  N-ary tree
  37. // where the  ordering   can  have a  specific  meaning.   The  first takes  no
  38. // arguments and initializes the pointer  and data  slots to NULL.   The second
  39. // takes an argument of type Type and initializes  the data slot to that value.
  40. // The third takes a reference to another D_Node object and duplicates the data
  41. // value, but not its children.
  42. //
  43. // The private  data section  contains just two  slots.  The  first is a Vector
  44. // object of some initial size "N"  that  contains pointers to  D_Node objects,
  45. // one for each  child.  The second  is a data slot  of type Type  to hold  the
  46. // value of the data item.
  47. //
  48. // Methods are provided to set and get the node data value, determine if a node
  49. // is a leaf or the root of some subtree,  and implement member-wise assignment
  50. // from one  D_Node to another via  the overloaded operator=. In  addition, the
  51. // brackets operator is overloaded to  provided  a mechanism to efficiently get
  52. // and set individual  subtree pointers in  a specific node,  thus allowing the
  53. // user to   control  the  orgranization  and  structure   of a tree.  Finally,
  54. // insertion, and removal  methods to allow the  user to control  placement and
  55. // ordering of sub-trees of a node are available.
  56. //
  57.  
  58. #ifndef D_NODEH                    // If no definition for class
  59. #define D_NODEH
  60.  
  61. #ifndef MISCELANEOUSH        // If we have not included this file,
  62. #include <misc.h>        // include miscelaneous useful definitions.
  63. #endif
  64.  
  65. #ifndef VECTORH                    // If no Vector class defined
  66. #include <cool/Vector.h>
  67. #endif
  68.  
  69. template <class Type, int nchild> CoolD_Node {
  70.   class CoolD_Node<Type,nchild>;            // Forward reference class
  71.   //class CoolN_Tree<CoolD_Node,Type,nchild>;        // Forward reference class
  72.   class CoolN_Tree_CoolD_Node_##Type##_##nchild;    // hack for noww
  73.   typedef Boolean (*Type##_CoolD_Node_Compare)(const Type&, const Type&);
  74.   typedef CoolD_Node<Type,nchild>* CoolD_Node_##Type##_##nchild##_p; // Pointer to class
  75.   DECLARE CoolVector<CoolD_Node<Type,nchild>*>;        // CoolVector of pointers to CoolD_Node
  76. }
  77.  
  78. template <class Type, int nchild>
  79. class CoolD_Node<Type,nchild> {
  80. public:
  81.   CoolD_Node<Type,nchild> ();            // Simple constructor
  82.   CoolD_Node<Type,nchild> (const Type& value);    // constructor with data value
  83.   CoolD_Node<Type,nchild> (const CoolD_Node<Type,nchild>&);    // Copy constructor
  84.   ~CoolD_Node<Type,nchild> ();            // Destructor
  85.  
  86.   inline void set (const Type&);        // Set node data to value
  87.   inline Type& get () const;            // Get node data value
  88.   Boolean is_leaf () const;            // TRUE if node has no children
  89.   inline CoolD_Node_##Type##_##nchild##_p& operator[] (int); // Set/Get pointers
  90.   inline int num_subtrees() const;         // number of subtree slots in node
  91.   
  92.   inline void set_compare (Type##_CoolD_Node_Compare = NULL); // Set compare
  93.   inline Boolean operator== (const Type&) const;     // Overload operator==
  94.   inline Boolean operator!= (const Type&) const;     // Overload operator!=
  95.   inline Boolean operator< (const Type&) const;         // Overload operator<
  96.   inline Boolean operator> (const Type&) const;         // Overload operator>
  97.   inline Boolean operator<= (const Type&) const;     // Overload operator<=
  98.   inline Boolean operator>= (const Type&) const;     // Overload operator>=
  99.  
  100.   CoolD_Node<Type,nchild>& operator= (const CoolD_Node<Type,nchild>&); // Assignment
  101.   Boolean insert_before (const CoolD_Node<Type,nchild>&, int);     // Insert before 
  102.   Boolean insert_after (const CoolD_Node<Type,nchild>&, int);      // Insert after
  103.  
  104. private:
  105.   CoolVector<CoolD_Node<Type,nchild>*> sub_trees; // Vector of subtree pointers
  106.   Type data;                    // Slot to hold data value
  107.   static Type##_CoolD_Node_Compare compare_s;    // Compare function for class
  108.  
  109.   CoolD_Node<Type,nchild>* copy_nodes(const CoolD_Node<Type,nchild>*) const; // Deep copy
  110.   void index_error (const char* fcn, int i);    // Raise exception
  111.  
  112.   //friend class CoolN_Tree<CoolD_Node,Type,nchild>;    // Friend class to access data
  113.   friend class CoolN_Tree_CoolD_Node_##Type##_##nchild;    // hack for noww
  114.   friend int Type##_default_CoolD_Node_compare (const Type&, const Type&);
  115. };
  116.  
  117.  
  118. // num_subtrees -- Returns number of slots available for subtrees in node
  119. // Input:          None
  120. // Output:         int length of the CoolVector allocated  for Subtrees.
  121.  
  122. template <class Type, int nchild>
  123. inline int CoolD_Node<Type,nchild>::num_subtrees () const {
  124.   return sub_trees.length();
  125. }
  126.  
  127.  
  128. // set -- Set value of data slot in node
  129. // Input: Reference to data slot value
  130. // Output: None
  131.  
  132. template <class Type, int nchild> 
  133. inline void CoolD_Node<Type,nchild>::set (const Type& value) {
  134.   this->data = value;                // Set data slot value
  135. }
  136.  
  137.  
  138. // get -- Get value of data slot in node
  139. // Input: None
  140. // Output: Reference to data slot value
  141.  
  142. template <class Type, int nchild> 
  143. inline Type& CoolD_Node<Type,nchild>::get () const {
  144.   return ((CoolD_Node<Type,nchild>*)this)->data; // Return data slot value
  145. }
  146.  
  147.  
  148. // set_compare -- Specify the comparison function to be used in logical tests
  149. //                of node data values
  150. // Input:         Pointer to a compare function
  151. // Output:        None
  152.  
  153. template <class Type, int nchild> 
  154. inline void CoolD_Node<Type,nchild>::set_compare (Type##_CoolD_Node_Compare c) {
  155.   if (c == NULL)
  156.     this->compare_s = &Type##_default_CoolD_Node_compare; // Default equality
  157.   else
  158.     this->compare_s = c;            // Else use one provided
  159. }
  160.  
  161.  
  162. // operator== -- Overload the equality operator to use the compare function
  163. // Input:        constant reference to Type value
  164. // Output:       TRUE/FALSE
  165.  
  166. template <class Type, int nchild> 
  167. inline Boolean CoolD_Node<Type,nchild>::operator== (const Type& value) const {
  168.   return ((((*this->compare_s)(this->data,value)) == 0) ? TRUE : FALSE);
  169. }
  170.  
  171.  
  172. // operator!= -- Overload the inequality operator to use the compare function
  173. // Input:        constant reference to Type value
  174. // Output:       TRUE/FALSE
  175.  
  176. template <class Type, int nchild> 
  177. inline Boolean CoolD_Node<Type,nchild>::operator!= (const Type& value) const {
  178.   return ((((*this->compare_s)(this->data,value)) == 0) ? FALSE : TRUE);
  179. }
  180.  
  181.  
  182. // operator< -- Overload the less than operator to use the compare function
  183. // Input:       constant reference to Type value
  184. // Output:      TRUE/FALSE
  185.  
  186. template <class Type, int nchild> 
  187. inline Boolean CoolD_Node<Type,nchild>::operator< (const Type& value) const {
  188.   return ((((*this->compare_s)(this->data,value)) < 0) ? TRUE : FALSE);
  189. }
  190.  
  191.  
  192. // operator> -- Overload the greater than operator to use the compare function
  193. // Input:       constant reference to Type value
  194. // Output:      TRUE/FALSE
  195.  
  196. template <class Type, int nchild> 
  197. inline Boolean CoolD_Node<Type,nchild>::operator> (const Type& value) const {
  198.   return ((((*this->compare_s)(this->data,value)) > 0) ? TRUE : FALSE);
  199. }
  200.  
  201.  
  202. // operator<= -- Overload the less than or equal operator to use the compare
  203. //               function
  204. // Input:        constant reference to Type value
  205. // Output:       TRUE/FALSE
  206.  
  207. template <class Type, int nchild> 
  208. inline Boolean CoolD_Node<Type,nchild>::operator<= (const Type& value) const {
  209.   return ((((*this->compare_s)(this->data,value)) > 0) ? FALSE : TRUE);
  210. }
  211.  
  212.  
  213. // operator>= -- Overload the greater than or equal operator to use the compare
  214. //               function
  215. // Input:        constant reference to Type value
  216. // Output:       TRUE/FALSE
  217.  
  218. template <class Type, int nchild> 
  219. inline Boolean CoolD_Node<Type,nchild>::operator>= (const Type& value) const {
  220.   return ((((*this->compare_s)(this->data,value)) < 0) ? FALSE : TRUE);
  221. }
  222.  
  223.  
  224. // operator[] -- Overload the brackets operator to provide a mechanism to set
  225. //               and/or get a sub-tree pointer of a node whose zero-relative
  226. //               index is specified from left to right
  227. // Input:        Zero-relative index into vector of sub-tree pointers
  228. // Output:       Reference to a pointer value
  229.  
  230. template <class Type, int nchild> 
  231. inline CoolD_Node_##Type##_##nchild##_p& CoolD_Node<Type,nchild>::operator[](int index) {
  232. #if ERROR_CHECKING
  233.   if (index >= this->num_subtrees())        // If index out of range
  234.     this->index_error ("operator[]", index);    // Raise exception
  235. #endif
  236.   return (this->sub_trees[index]);
  237. }
  238.  
  239.  
  240.  
  241. #endif                        // End D_NODEH #if
  242.